package 代码随想2._11单调栈;

/**
 * @author XXX
 * @date 2024-01-18 9:45
 */

import java.util.Deque;
import java.util.LinkedList;

/**
 * https://leetcode.cn/problems/daily-temperatures/description/
 * 通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。
 */
public class _1每日温度 {
    public int[] dailyTemperatures(int[] temperatures) {
        int lens = temperatures.length;
        int[] answer = new int[lens];

        Deque<Integer> dq = new LinkedList<>();
        dq.push(0);
        for (int i=1;i<lens;i++){
            if (temperatures[i]<=temperatures[dq.peek()]){
                dq.push(i);
            }else {
                while (!dq.isEmpty() && temperatures[i] > temperatures[dq.peek()]){
                    answer[dq.peek()] = i - dq.peek();
                    dq.pop();
                }
                dq.push(i);
            }
        }
        return answer;
    }
    //精简
    public int[] dailyTemperatures2(int[] temperatures) {
        int len = temperatures.length;
        int[] answer = new int[len];
        Deque<Integer> dq = new LinkedList<>();
        for (int i=0; i<len; i++){
            while (!dq.isEmpty() && temperatures[dq.peek()]<temperatures[i]){
                answer[dq.peek()] = i - dq.pop();
            }
            dq.push(i);
        }
        return answer;
    }
}

class Test{
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] answer = new int[len];
        Deque<Integer> dq = new LinkedList<>();
        for (int i=0; i<len; i++){
            while (!dq.isEmpty() && temperatures[i]>temperatures[dq.peek()])
                answer[dq.peek()] = i - dq.pop();
            dq.push(i);
        }
        return answer;
    }
}